class Solution {
public:
    string longestPalindrome(string s) {
        // int ret = 0;
        // pair<int,int> ss;
        // vector<vector<int> > dp(s.size(),vector<int>(s.size(),0));
        // for(int i = 0;i < s.size();i++){
        //     dp[i][i] = 1;
        // }
        // for(int i = s.size() - 1;i >= 0;i--){
        //     for(int j = i + 1;j < s.size();j++){
        //         if(s[i] == s[j]){
        //             if(j - i <= 1 || dp[i+1][j-1] == 1){
        //                 dp[i][j] = 1;
        //                 if(j - i + 1 > ret){
        //                     ret = j - i + 1;
        //                     ss.first = i;
        //                     ss.second = j;
        //                 }
        //             }
        //         }
        //     }
        // }
        // return string(s.begin()+ss.first,s.begin()+ss.second+1);
        
        string ss;
        for(int i = 0;i < s.size();i++){
            ss += '#';
            ss += s[i];
        }
        ss += '#';
        
        vector<int> P(ss.size(),1);
        int R = 0;
        int C = 0;
        int Max = 0;
        
        int l = 0;
        for(int i = 1;i < ss.size();i++){
           
            if(R > i){
                P[i] = min(R - i,P[2 * C - i]);
            }else{
                P[i] = 1;
            }
            
            while(i>=P[i] && i+P[i] < ss.size() && ss[i-P[i]]==ss[i+P[i]]){
              
                P[i]++;
            }
            
            if(P[i] + i > R){
                R = P[i] + i;
                C = i;
            }
            if(P[i] > Max){
                Max = P[i] - 1;
                l = (C - Max) / 2;
            }
        }
        
        return string(s.begin()+l,s.begin()+l+Max);
    }
};
